package LeetCodeHot100TopInterview;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Q023_MergeKList {


    //合并K 个有序链表
    //使用小根堆..
//    public ListNode mergeKLists(ListNode[] lists) {
//
//        if (lists == null || lists.length == 0){
//            return null;
//        }
//
//        //小根堆
//        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
//            @Override
//            public int compare(ListNode o1, ListNode o2) {
//                return o1.val - o2.val;
//            }
//        });
//
//        //所有头进入小根堆
//        for (ListNode head : lists) {
//            if (head != null)
//            queue.add(head);
//        }
//        if (queue.size() == 0) {
//            return null;
//        }
//        ListNode ans = queue.poll();
//        ListNode ret = ans;
//        if (ans.next != null){
//            queue.add(ans.next);
//        }
//
//
//        while (!queue.isEmpty()) {
//            ListNode node = queue.poll();
//            ans.next = node;
//            ans = node;
//            if (node.next != null) {
//                queue.add(node.next);
//            }
//        }
//
//        return ret;
//
//        }

    //也 ok 但注意断开连接
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists == null || lists.length == 0){
            return null;
        }

        //小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        //所有头进入小根堆
        for (ListNode head : lists) {
            if (head != null) {
                queue.add(head);
                head = head.next;
                while (head != null) {
                    queue.add(head);
                    head = head.next;
                }
            }
        }





        if (queue.size() == 0) {
            return null;
        }
        ListNode ans = new ListNode(0);
        ListNode ret = ans;

        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            //需要断开连接 不然会出现死循环
            node.next = null;
            ans.next = node;
            ans = node;
        }

        return ret.next;

    }

    public static void main(String[] args) {
        Q023_MergeKList fun = new Q023_MergeKList();
        ListNode[] arg = new ListNode[2];
        ListNode head1 = new ListNode(-2);
        head1.next = new ListNode(-1);
        head1.next.next = new ListNode(-1);
        head1.next.next.next = new ListNode(-1);
        ListNode head2 = null;
//        head1.next = new ListNode(2);
        arg[0] = head1;
        arg[1] = head2;
        System.out.println(fun.mergeKLists(arg).val);
    }

    }

